/** **********************************************************************************
 * @file    1.A.c
 * @mainpage
 * @date    2013-09-29 22:33
 * @author  Alexey Kulikov <alexeyqu@gmail.com>, group 376, DCAM MIPT
 * @version 1.00
 *
 * Find prime numbers in the input stream.
 *
 * @par     The task.
 *          The program gets amount of (probably) prime numbers and numbers.
 *          It searches prime numbers in the input stream and prints them.
 *
 * @note    NB: the global is-prime-check is performed before receiving of numbers to
 *          prevent time loss.
 *
 * @warning Consider that amount of numbers is positive and lower than 10000 and
 *          numbers are positive also and lower than 100001
**************************************************************************************/

#include <stdlib.h>
#include <stdio.h>

#define MAX_NUMBER 100001
#define DEBUG
#define IS_COMPOSITE(x) ( (x % 2 == 0 && x != 2) || Iscomposite[x] == 1 )

#ifdef DEBUG
    #define DBG printf ("# "),
    #define ASSERT(cond)                                                              \
    if (!(cond))                                                                      \
    {                                                                                 \
        printf ("Critical failure in assertion '%s'! \nfile %s, line %d \n"           \
                "Now keep calm and EXTERMINATE! EXTERMINATE! EXTERMINATE!!!\n"        \
                , #cond, __FILE__, __LINE__);                                         \
        abort();                                                                      \
    }
#else
    #define DBG if (0)
    #define ASSERT(cond)
#endif

/** ********************************************************************************
 * Find_Composites - finds prime numbers in fixed interval using Sieve of Eratosthenes method
 *
 * @param   Iscomposite  Array storing info about primality of numbers
 *          from 0 to MAX_NUMBER = 100001
 *
 * @note    Memory and time usage are equally low for different numbers according to task
 * @note    1 is considered as prime
************************************************************************************/
void Find_Composites (char Iscomposite[]);

int main()
{
    DBG printf ("C language test'07. \n");
    DBG printf ("1.A problem. \n");
    DBG printf ("Search for prime numbers in input stream. \n");
    DBG printf ("Enter the amount of numbers: \n-> ");

    char Iscomposite[MAX_NUMBER] = {0}; //!< 1 - if element i is composite, else - 0
    int numAmount = 0; //!< Amount of numbers
    int res = 0; //!< Value to control correct input

    res = scanf ("%d", &numAmount);
    ASSERT (res); ASSERT (numAmount >= 0); ASSERT (numAmount < 10000);

    Find_Composites (Iscomposite);

    int i = 0; //!< Counter
    long long x = 0; //!< each number in input

    DBG printf ("Enter all numbers separated by spaces in one line\n (the result will appear on next line): \n-> ");

    for (i = 0; i < numAmount; i++)
    {
        res = scanf ("%lld", &x);
        ASSERT (res);

        ASSERT (x > 0);
        ASSERT (x < MAX_NUMBER);
        if (!IS_COMPOSITE (x)) printf ("%lld ", x);
    }

    return 0;
}

void Find_Composites (char Iscomposite[])
{
    long i = 0, j = 0; //!< Counters

    for (i = 2; i < MAX_NUMBER; i++)
    {
        if (Iscomposite[i] == 0)
        {
            for (j = i*2; j < MAX_NUMBER; j += i)
            {
                Iscomposite[j] = 1;
            }
        }
    }
}
